//
// Created by 66477 on 2022/9/24.
//

#ifndef DATA_STRUCTURE_LIST3_3_H
#define DATA_STRUCTURE_LIST3_3_H

#include "Node3_3.h"

class List3_3 {
private:
    Node3_3 *head = nullptr;
public:

    /**
     * 头插
     * @param x 插入的值
     * @return
     */
    List3_3 *insert(char x) {
        Node3_3 *n = new Node3_3(x), *p = head;
        if (head == nullptr) {
            head = n;
        } else {
            while (p->getNext() != nullptr && !(p->getFrep() > 0 && p->getNext()->getFrep() == 0)) {
                p = p->getNext();
            }
            if (p->getNext() != nullptr) {
                n->setNext(p->getNext());
                p->getNext()->setPrior(n);
            }
            n->setPrior(p);
            p->setNext(n);
        }
        return this;
    }

    /**
     * 搜索元素，增加元素的频度值并使节点前移，如果表里没有此元素就新加入
     * @param x 搜索值
     * @return
     */
    List3_3 *locate(char x) {
        if (head == nullptr) {
            insert(x);
            return this;
        } else {
            Node3_3 *p = head;
            while (p != nullptr) {
                if (p->getData() == x) {
                    break;
                }
                p = p->getNext();
            }
            if (p == nullptr) {
                insert(x);
                return this;
            }
            p->addFrep();
            while (p->getPrior() != nullptr) {
                if (p->getPrior()->getFrep() <= p->getFrep()) {
                    Node3_3 *q = p->getPrior();
                    if (p->getNext() != nullptr) {
                        p->getNext()->setPrior(q);
                    }
                    if (q->getPrior() != nullptr) {
                        q->getPrior()->setNext(p);
                    }
                    p->setPrior(p->getPrior()->getPrior());
                    q->setNext(q->getNext()->getNext());
                    p->setNext(q);
                    q->setPrior(p);
                    if (q == head) {
                        head = p;
                    }
                } else {
                    break;
                }
            }
        }
        return this;
    }

    /**
     * 打印链表
     * @return
     */
    List3_3 *print() {
        cout << "Q3 List:";
        if (head != nullptr) {
            Node3_3 *q = head;
            while (q != nullptr) {
                cout << q->getData() << "(" << q->getFrep() << ")" << " ";
                q = q->getNext();
            }
        }
        cout << endl;
        return this;
    }
};

#endif //DATA_STRUCTURE_LIST3_3_H
